package 强化训练;

public class 数组中出现超过一半得数字 {
    public int MoreThanHalfNum_Solution(int [] array) {
        //先对数组进行排序
        quickSort(array,0,array.length-1);
        return array[array.length / 2];
    }
    private void quickSort(int[] arr,int l,int r){
        if(l >= r) return;
        int p = help(arr,l,r);
        quickSort(arr,l,p-1);
        quickSort(arr,p+1,r);
    }
    private int help(int[] arr,int l ,int r){
        int j = l;//小于tem得元素，[l,j],大于tem得元素[j+1,i)
        int tem = arr[l];
        for(int i = j + 1;i <= r;i++){
            if(arr[i] < tem){
                swap(arr,i,j+1);
                j++;
            }
        }
        swap(arr,l,j);
        return j;
    }
    private void swap(int[] arr,int i ,int j){
        int tem = arr[i];
        arr[i] = arr[j];
        arr[j] = tem;
    }
}
